COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00008 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a60.tex[106,phy] \today\hfill}

\bigskip
\line{CS 106 [Dynamic Programming\hfill}
\line{\bf Example.\hfill}

We have a string in the character array  {\tt S[1..N]}  
which we want to test for being
a legitimate Pascal assignment command.  We will simplify the problem by only
allowing simple variables, positive integer constants, addition, multiplication,
and parentheses. The defining rules are:

\smallskip\disleft 25pt:
(1): A command  ($C$)  is a variable  ($V$), 
followed by `$:=$', followed by an
expression  ($E$), followed by a semicolon.  In abbreviated form  
$C\sim  V:=E$;

\smallskip\disleft 25pt:
(2): An expression is a sum of one or more terms (to be defined next).  That is,
it is either a term, or is a (shorter) expression followed by  `$+$'  
followed by a (shorter) term.

\smallskip\halign{\qq\qq\lft{\tt #}\cr
$E\sim  T \quad {\rm or}\quad  E + T$\cr}

\smallskip\disleft 25pt:
(3): A term is a product of one or more factors  ($F$) (to be defined next):

\smallskip\halign{\qq\qq\lft{\tt #}\cr
$T\sim F \quad {\rm or}\quad  T\times F$\cr}

\smallskip\disleft 25pt:
(4): A factor is a number ($N$), a variable ($V$), 
or an expression with parentheses around it.		

\smallskip\halign{\qq\qq\lft{\tt #}\cr
$F\sim  N\quad  {\rm or}\quad  V \quad{\rm or}\quad (E)$.\cr}

\smallskip\disleft 25pt:
(5): A number is a digit or $\ldots$

\smallskip\disleft 25pt:
(6): A variable is a letter or $\ldots$

\smallskip
Using dynamic programming, we will test every segment (substring) of the string
to see whether it belongs to one or more of the above types.  For each type, we
have a boolean array, indexed by the endpoints of the segments, to record whether
each segment belongs to the type.  For example, the array element  
{\tt V[START, LENGTH]}
will be true if  {\tt S[START..START+LENGTH-1]} 
is a variable by the above definitions.

The algorithm initializes the arrays to false.  Then the letter and digit arrays are
set true where appropriate:

\smallskip\halign{\qq\qq\lft{\tt #}\cr
	FOR I:=1 TO N DO\cr
\q		BEGIN\cr
\q		IF ('A'<=S[I]) AND (S[I]<='Z') (* ASSUMES ASCII CODE *)\cr
\qq			THEN L[I,1]:=TRUE\cr
\q		ELSE IF ('O'<=S[I]) AND (S[I]<='9')\cr
\qq			THEN D[I,1]:=TRUE\cr
\q		END\cr}


\vfill\eject

\noindent
Then the main iteration tests each segment, in order of increasing length:


\smallskip\halign{\qq\qq\lft{\tt #}\cr
	FOR LENGTH:=1 TO N DO\cr
	FOR START:=1 TO N+1-LENGTH DO\cr
\noalign{\smallskip}
\q		BEGIN\cr
\q		IF L[START,LENGTH]THEN\cr
\qq			V[START,LENGTH]:=TRUE;\cr
\q		FOR SHORTER:=1 TO LENGTH-1 DO (* ONLY LENGTH -1 WILL WORK *)\cr
\qq			IF V[START,SHORTER] AND\cr
\qq\q				L[START+SHORTER,LENGTH-SHORTER]\cr
\qq			THEN V[START,LENGTH]:=TRUE;\cr
\noalign{\smallskip}
\q		IF V[START,LENGTH]THEN\cr
\qq			F[START,LENGTH]:=TRUE;\cr
\noalign{\smallskip}
\q		IF E[START+1.;LENGTH-2] AND\cr
\qq			(S[START]='(') AND (S[START+LENGTH-1=')')\cr
\qq			THEN F[START,LENGTH]:=TRUE\cr
\noalign{\smallskip}
\q		FOR SHORTER:=1 TO LENGTH-2 DO\cr
\qq			IF T[START,SHORTER] AND (S[START+SHORTER]='*')\cr
\qq\q				AND F[START+SHORTER+1,LENGTH-SHORTER-1]\cr
\noalign{\smallskip}
\qq			THEN T[START,LENGTH]:=TRUE\cr
\noalign{\smallskip}
\qq			etc.\cr
\q		END\cr}

\smallskip
When done, we check whether  {\tt C[1,N]} is true.  If so, the string is a correct
assignment command.  Nothing to it.






\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft March 28, 1984

\bye